#include<iostream>
#include<string.h>
#include<stdlib.h>
using namespace std;
//递归
//1.正序输出无符号数的每一位
void ForwardPrintDig(int n)
{
  //4321 -> 432 -> 43 -> 4  递归回来的时候再输出最后一位
  if(n > 9)
    ForwardPrintDig(n / 10);

  cout << n % 10 << " ";
}
//2.逆序输出无符号数的每一位
void ReversePrintDig(int n)
{
  //4321 输出 1  -> 432 输出2  -> 43 输出3  ->4 输出4 
  if(n == 0)
    return ;
  cout << n % 10 << " ";
  ReversePrintDig(n / 10);
}
//3.实现strlen -递归+非递归
size_t strlen_1(const char* str)//方法1:计数器
{
    int count = 0;
    while(*str != '\0')
    {
        count++;
        str ++;
    }
    return count;
}
size_t strlen_2(const char* str) //方法2:指针-指针
{
    const char* end = str;
    while(*end != '\0') 
        end++;
    return end- str;
}
size_t strlen_3(const char* str) //方法3:递归
{
    if(*str != '\0')
        return 1 + strlen_3(str+1);
    else
        return 0;
}
//4.递归实现字符串逆序
void ReverseString(char* str)
{
    int len = strlen(str);
    char tmp  = str[0];//保存当前第一个字符
    *str = *(str + len - 1);//最后一个字符换到第一个位置
    *(str + len - 1) = '\0'; //为了下一轮的递归,先把当前最后一个字符置为\0
    
    if(strlen(str+1) >= 2)
        ReverseString(str+1);
    
    *(str+len-1) = tmp;//原来保存的第一个字符换到最后 
}
//5.递归求整数拆分成每一位后的和
int SplitNum(int n)
{
    //D(1234) = 4 + D(123) = 4 + 3 + D(12) = 4+3+2 + D(1)  = 4 + 3 + 2 +1 + D(0)
    if(n != 0)
        return n % 10 + SplitNum(n/10);
    else
        return 0;
}
//6.递归计算n的k次方
//k > 0 PowK(n,k) = n*PowK(n,k-1)
//k == 0  1
//k < 0  PowK(n,k) = 1 / PowK(n,-k);     2^(-2) = 1/ 2 ^ 2
double PowK(int n,int k)
{
    if(k == 0)
        return 1;
    else if(k > 0)
        return n* PowK(n,k-1);
    else 
        return 1/PowK(n,-k);
}

//7.汉诺塔问题
void move(char pos1,char pos2)
{
    cout << pos1 <<"  move to  "<< pos2 << endl;
}

//n:盘子数 pos1:起始位置  pos2:中转位置 pos3:目的位置
//步骤1:将A盘上的n-1个盘子通过C盘移动到B盘
//步骤2:将A盘上剩余的1个盘子直接移动到C盘
//步骤3:将B盘上的n-1个盘子通过A盘移动C盘
//pos1:A盘 pos2:B盘 pos3:C盘
void Hanoi(int n,char pos1,char pos2,char pos3)
{
    if(n == 1)
    {
        move(pos1,pos3);
    }
    else
    {
        Hanoi(n-1,pos1,pos3,pos2);
        move(pos1,pos3);
        Hanoi(n-1,pos2,pos1,pos3);
    }
}
//8.青蛙跳台阶-一次可以跳2阶
int FrogStepTwo(int n) //n:有多少阶台阶
{
    //有n阶台阶,一次可以跳2阶,假设跳上n阶台阶的方法数为:f(n)
    //case1:第一次跳1阶,剩余的跳上n-1阶台阶的方法数为:f(n-1)
    //case2:第一次跳2阶,剩余的跳上n-2阶台阶的方法数为:f(n-2)
    if(n == 0 )
        return 0;
    else if(n == 1)
        return 1;
    else if(n == 2)
        return 2;
    else 
        return FrogStepTwo(n-1) + FrogStepTwo(n-2);
}
//9.青蛙跳台阶-一次可以跳3阶
int FrogStepThree(int n)
{
    //如果有1阶台阶:方法数为1   2阶台阶:方法数为2   3阶台阶:方法数为4 (1,1,1) (1,2) (2,1) (3)
    //有n阶台阶,一次可以跳3阶,假设跳上n阶台阶的方法数为:f(n)
    //case1:第一次跳1阶,剩余的跳上n-1阶台阶的方法数为:f(n-1)
    //case2:第一次跳2阶,剩余的跳上n-2阶台阶的方法数为:f(n-2)
    //case3:第一次跳3阶,剩余的跳上n-3阶台阶的方法数为:f(n-3)
    if(n == 0)
        return 0;
    else if(n == 1)
        return 1;
    else if(n == 2)
        return 2;
    else if(n == 3)
        return 4;
    else 
        return FrogStepTwo(n-1) + FrogStepTwo(n-2) + FrogStepThree(n-3);
}
//结论:如果一次可以跳k级台阶 那么跳上n阶台阶的方法数f(n) = f(n-1) + .... + f(n-k),但是需要写出 if(n == 0) ... if(n == k)时候的方法数
int main()
{
    int n = 3;
    Hanoi(n,'A','B','C');
    // while(cin >> n)
    // {
    //     cout << PowK(2,n) << endl;
    //     // ForwardPrintDig(n);
    //     // cout << endl;
    //     // ReversePrintDig(n);
    //     // cout << endl;
    //     // cout << SplitNum(n) << endl;
    // }
    // char str[10];
    // while(cin >> str)
    // {
    //     cout << strlen(str) <<" " <<strlen_1(str) <<" " << strlen_2(str) <<" " << strlen_3(str) << endl;

    //     ReverseString(str);
    //     cout << str << endl;
    // }
    
    return 0;
}
